package LeetCode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

public class LC_105_ConstructBinaryTreefromPreorderandInorderTraversal {
    public static void main(String[] args) {

    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution_1 {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0) return null;
            HashMap<Integer, Integer> inorderMap = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode root = new TreeNode(preorder[0]);
            stack.push(root);
            for (int i = 1; i < preorder.length; i++) {
                TreeNode top = stack.peek();
                int indexTop = inorderMap.get(top.val);
                int indexVal = inorderMap.get(preorder[i]);
                TreeNode node = new TreeNode(preorder[i]);
                if (indexVal < indexTop)
                    top.left = node;
                else {
                    while (indexVal > indexTop) {
                        top = stack.pop();
                        indexTop = stack.isEmpty() ? Integer.MAX_VALUE : inorderMap.get(stack.peek().val);
                    }
                    top.right = node;
                }
                stack.push(node);
            }
            return root;
        }
    }

    static class Solution_2 {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0) return null;
            if (inorder == null || inorder.length == 0) return null;
            if (preorder.length != inorder.length) return null;
            return build(preorder, inorder, 0, 0, inorder.length - 1);
        }

        private TreeNode build(int[] preorder, int[] inorder, int preIndex, int startInIndex, int endInIndex) {
            if (endInIndex < startInIndex) return null;
            TreeNode node = new TreeNode(preorder[preIndex]);

            int index = getIndexInInorder(inorder, preorder[preIndex]);
            int lenL = index - startInIndex;
            int lenR = endInIndex - startInIndex - lenL;

            if (lenL > 0) node.left = build(preorder, inorder, preIndex + 1, startInIndex, index - 1);
            if (lenR > 0)
                node.right = build(preorder, inorder, preIndex + lenL + 1, index + 1, endInIndex);
            return node;
        }

        private int getIndexInInorder(int[] inorder, int val) {
            for (int i = 0; i < inorder.length; i++)
                if (val == inorder[i]) return i;
            return -1;
        }
    }

}
